#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDataType;

typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* front;
	QNode* rear;
	int size;
}Queue;

typedef struct {
	Queue q1;
	Queue q2;
} MyStack;

void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("newnode malloc fault");
		return;
	}
	newnode->data = data;
	newnode->next = NULL;

	if (q->rear == NULL)
	{
		q->front = q->rear = newnode;
	}
	else
	{
		q->rear->next = newnode;
		q->rear = newnode;
	}
	q->size++;
}

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->size > 0);

	return q->front->data;
}

int QueueSize(Queue* q)
{
	assert(q);

	return q->size;
}

QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->size > 0);

	return q->rear->data;
}

int QueueEmpty(Queue* q)
{
	assert(q);

	return !(q->size);
}

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->front;

	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	cur = NULL;
	q->front = q->rear = NULL;
	q->size = 0;
}

void QueuePop(Queue* q)
{
	assert(q);
	assert(q->size > 0);

	QNode* del = q->front;
	q->front = q->front->next;

	free(del);
	del = NULL;

	q->size--;
	if (q->size == 0)
		q->rear = NULL;
}

void QueueInit(Queue* q)
{
	assert(q);
	q->front = q->rear = NULL;
	q->size = 0;
}

MyStack* myStackCreate() {
	MyStack* ST = (MyStack*)malloc(sizeof(MyStack));
	if (ST == NULL)
	{
		perror("malloc");
		return;
	}
	QueueInit(&ST->q1);
	QueueInit(&ST->q2);
	return ST;
}

void myStackPush(MyStack* obj, int x) {
	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}

int myStackPop(MyStack* obj) {
	Queue* emptyq = &obj->q1;
	Queue* noemptyq = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		emptyq = &obj->q2;
		noemptyq = &obj->q1;
	}

	while (QueueSize(noemptyq) > 1)
	{
		QueuePush(emptyq, QueueFront(noemptyq));
		QueuePop(noemptyq);
	}

	QDataType top = QueueFront(noemptyq);
	QueuePop(noemptyq);
	return top;
}

int myStackTop(MyStack* obj) {
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

bool myStackEmpty(MyStack* obj) {
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);
	free(obj);
}

int main()
{
	MyStack* obj = myStackCreate();
	myStackPush(obj, 3);
	int param_2 = myStackPop(obj);
	int param_3 = myStackTop(obj);
	bool param_4 = myStackEmpty(obj);
	myStackFree(obj);
	return 0;
}